package findMaxForm

import (
	"fmt"
	"sort"
	"strconv"
)

// leetcode 474 1和0，找到其中各自数量的最大子集数量集合

func findMaxForm(strs []string, m int, n int) int {
	sort.Slice(strs, func(i, j int) bool {
		return len(strs[i]) < len(strs[j])
	})
	dp := make([][]int, m+1)
	// 初始化dp，其中元素的含义是最大子集数量
	for i := 0; i < len(dp); i++ {
		cur := make([]int, n+1)
		cur[0] = 1
		dp[i] = cur
	}
	for i := 1; i < len(dp[0]); i++ {
		dp[0][i] = 1
	}
	fmt.Println(strs, len(dp), len(dp[0]))
	for i := 1; i < len(dp); i++ {
		for j := 1; j < len(dp[0]); j++ {
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + exist(strs, i, j)
		}
	}
	fmt.Println(dp)
	return 0
}

func exist(nums []string, m, n int) int {
	total := 0
	for _, v := range nums {
		if len(v) == m+n {
			if sum([]rune(v)) == n {
				total++
			}
			fmt.Println(v, len(v), m, n, m+n, sum([]rune(v)), n, total)
		}
	}
	return total
}

func sum(nums []rune) int {
	cur := 0
	for i := 0; i < len(nums); i++ {
		num, _ := strconv.Atoi(string(nums[i]))
		cur += num
	}
	//fmt.Println(cur)
	return cur
}

func tongyi(strs []string, m, n int) int {
	dp := make([][]int, m+1)
	for i, _ := range dp {
		dp[i] = make([]int, n+1)
	}
	// 初始化之后进行按照字符串的数字类型数量计算
	counts := make([][2]int, len(strs))
	for i, s := range strs {
		for _, x := range s {
			if x == '0' {
				counts[i][0] += 1
			} else if x == '1' {
				counts[i][1] += 1
			}
		}
	}
	fmt.Println(counts)
	// 计算完之后进行dp设置
	for i := 0; i < len(strs); i++ {
		x, y := counts[i][0], counts[i][1]
		for j := m; j >= x; j-- {
			for k := n; k >= y; k-- {
				dp[j][k] = max(dp[j][k], dp[j-x][k-y]+1)
			}
		}
	}
	fmt.Println(dp)
	return dp[m][n]
}
